// using System.Collections.Generic;
// using UnityEngine;
// using Unity.Collections;
// using Unity.Entities;
// using Unity.Mathematics;

// namespace JPS {
// 	internal struct JPSPlusNode:IComponentData{
// 		public Vector2Int Location { get; private set; }
// 		public float GivenCost { get; set; }
// 		public float FinalCost { get; set; }
// 		public int[] Dist { get; private set; }
// 		// 第一位为Straight
// 		// 第二位为Primary
// 		public bool[] Send { get; set; }
// 		public bool[] Recv { get; set; }
// 		public bool IsPrimary { get; set; }
// 		public bool IsStraight { get; set; }
// 		public uint ListState { get; set; }
// 		public int Parent { get; set; }
// 		public JPSDir dirFromParent { get; set; }

// 		public JPSPlusNode(int x, int y) : this(new Vector2Int(x, y)) { }
// 		public JPSPlusNode(Vector2Int l) {
// 			Dist = new int[8];
// 			Send = new bool[8];
// 			Recv = new bool[8];
// 			for (int i = 0; i < 8; i++) {
// 				Dist[i] = int.MinValue;
// 				Send[i] = false;
// 				Recv[i] = false;
// 			}
// 			Location = l;
// 			IsPrimary = false;
// 			IsStraight = false;
// 		}

// 		public void Revert() {
// 			GivenCost = 0;
// 			FinalCost = 0;
// 			Parent = null;
// 			ListState = 0;
// 		}
// 	}

// 	internal class JPSPlusGrid {
// 		// 边界设定
// 		private readonly int _boundsMaxX;
// 		private readonly int _boundsMaxY;
// 		private readonly int _boundsMinX;
// 		private readonly int _boundsMinY;

// 		// 实际内容
// 		private readonly bool[,] _navigable;
// 		public readonly JPSPlusNode[,] _grid;

// 		internal JPSPlusNode this[int x, int y] => _grid[x, y];
// 		internal JPSPlusNode this[Vector2Int x] => _grid[x.x, x.y];

// 		public JPSPlusGrid(bool[,] navigable) {
// 			_boundsMinX = 0;
// 			_boundsMaxX = navigable.GetUpperBound(0);
// 			_boundsMinY = 0;
// 			_boundsMaxY = navigable.GetUpperBound(1);
// 			_navigable = navigable;

// 			_grid = new JPSPlusNode[_boundsMaxX + 1, _boundsMaxY + 1];
// 			for (var x = _boundsMinX; x <= _boundsMaxX; x++)
// 				for (var y = _boundsMinY; y <= _boundsMaxY; y++)
// 					_grid[x, y] = new JPSPlusNode(x, y);
// 			CalcPrimaryJP();
// 			CalcStraightJP();
// 			CalcNonDiagonalDist();
// 			CalcDiagonalDist();
// 			CalcWallDist();
// 		}

// 		private void CalcWallDist() {
// 			for (var x = _boundsMinX; x <= _boundsMaxX; x++) {
// 				SetWallDist(x, _boundsMinY - 1, (int)JPSDir.N, 0);
// 				SetWallDist(x, _boundsMinY - 1, (int)JPSDir.NW, 0);
// 				SetWallDist(x, _boundsMinY - 1, (int)JPSDir.NE, 0);
// 				SetWallDist(x, _boundsMaxY + 1, (int)JPSDir.S, 0);
// 				SetWallDist(x, _boundsMaxY + 1, (int)JPSDir.SW, 0);
// 				SetWallDist(x, _boundsMaxY + 1, (int)JPSDir.SE, 0);
// 			}
// 			for (var y = _boundsMinY; y <= _boundsMaxY; y++) {
// 				SetWallDist(_boundsMinX - 1, y, (int)JPSDir.E, 0);
// 				SetWallDist(_boundsMinX - 1, y, (int)JPSDir.SE, 0);
// 				SetWallDist(_boundsMinX - 1, y, (int)JPSDir.NE, 0);
// 				SetWallDist(_boundsMaxX + 1, y, (int)JPSDir.W, 0);
// 				SetWallDist(_boundsMaxX + 1, y, (int)JPSDir.SW, 0);
// 				SetWallDist(_boundsMaxX + 1, y, (int)JPSDir.NW, 0);
// 			}
// 			SetWallDist(_boundsMinX - 1, _boundsMinY - 1, (int)JPSDir.NE, 0);
// 			SetWallDist(_boundsMaxX + 1, _boundsMinY - 1, (int)JPSDir.NW, 0);
// 			SetWallDist(_boundsMinX - 1, _boundsMaxY + 1, (int)JPSDir.SE, 0);
// 			SetWallDist(_boundsMaxX + 1, _boundsMaxY + 1, (int)JPSDir.SW, 0);
// 		}

// 		private void SetWallDist(int x, int y, int dirIdx, int dist) {
// 			var offset = JPSUtils.DirToVec[dirIdx];
// 			int nx = x + offset.x, ny = y + offset.y;
// 			// 超出范围，一律中断
// 			if (!InBounds(nx, ny)) return;
// 			// 命中障碍物，重新开始递归
// 			if (!_N(nx, ny)) {
// 				SetWallDist(nx, ny, dirIdx, 0);
// 				return;
// 			}
// 			// 对角线情况下出现
// 			// 0 0
// 			// 0 x
// 			// 这种情况需要把dist归零
// 			if (dirIdx >= 4) {
// 				if (!_N(nx, y) || !_N(x, ny))
// 					dist = 0;
// 			}
// 			var cell = this[nx, ny];
// 			var oppDirIdx = JPSUtils.OppositeDirIdx[dirIdx];
// 			if (cell.Dist[oppDirIdx] == int.MinValue || cell.Dist[oppDirIdx] < dist)
// 				cell.Dist[oppDirIdx] = dist;
// 			SetWallDist(nx, ny, dirIdx, dist - 1);
// 		}

// 		private void CalcDiagonalDist() {
// 			// 收集跳点并沿对角线防线发散
// 			for (var x = _boundsMinX; x <= _boundsMaxX; x++)
// 				for (var y = _boundsMinY; y <= _boundsMaxY; y++) {
// 					var cell = this[x, y];
// 					if (cell.IsPrimary || cell.IsStraight) {
// 						bool[] dds = new bool[4];
// 						if (cell.Send[(int)JPSDir.N])
// 							dds[1] = dds[2] = true;
// 						if (cell.Send[(int)JPSDir.E])
// 							dds[2] = dds[3] = true;
// 						if (cell.Send[(int)JPSDir.S])
// 							dds[0] = dds[3] = true;
// 						if (cell.Send[(int)JPSDir.W])
// 							dds[0] = dds[1] = true;
// 						for (int i = 0; i < 4; i++) {
// 							int dirIdx = i + 4;
// 							if (dds[i])
// 								SetDiagonaDist(x, y, dirIdx, 1);
// 						}
// 					}
// 				}

// 		}

// 		private void SetDiagonaDist(int x, int y, int dirIdx, int dist) {
// 			var offset = JPSUtils.DirToVec[dirIdx];
// 			int nx = x + offset.x, ny = y + offset.y;
// 			if (!_N(nx, ny) || !_N(nx, y) || !_N(x, ny)) return;
// 			var cell = this[nx, ny];
// 			var oppDirIdx = JPSUtils.OppositeDirIdx[dirIdx];
// 			if (cell.Dist[oppDirIdx] == int.MinValue || cell.Dist[oppDirIdx] > dist)
// 				cell.Dist[oppDirIdx] = dist;
// 			SetDiagonaDist(nx, ny, dirIdx, dist + 1);
// 		}

// 		private void CalcNonDiagonalDist() {
// 			// 收集所有跳点并开始发散
// 			for (var x = _boundsMinX; x <= _boundsMaxX; x++)
// 				for (var y = _boundsMinY; y <= _boundsMaxY; y++) {
// 					var cell = this[x, y];
// 					if (cell.IsPrimary || cell.IsStraight)
// 						for (int dirIdx = 0; dirIdx < 4; dirIdx++)
// 							if (cell.Send[dirIdx])
// 								cell.Dist[dirIdx] = GetDistToNextJumpPoint(x, y, dirIdx);
// 				}
// 		}

// 		int GetDistToNextJumpPoint(int x, int y, int dirIdx) {
// 			Vector2Int dirVec = JPSUtils.DirToVec[dirIdx];
// 			int nx = x + dirVec.x, ny = y + dirVec.y;
// 			int dist = 0;
// 			while (_N(nx, ny)) {
// 				dist++;
// 				var cell = this[nx, ny];
// 				if (cell.IsPrimary) {
// 					var oppDirIdx = JPSUtils.OppositeDirIdx[dirIdx];
// 					if (cell.Recv[oppDirIdx])
// 						break;
// 				}
// 				nx = nx + dirVec.x;
// 				ny = ny + dirVec.y;
// 			}
// 			if (dist == 0)
// 				dist = int.MinValue;
// 			return dist;
// 		}

// 		private void CalcStraightJP() {
// 			// 收集所有的跳点，并开始发散
// 			for (var x = _boundsMinX; x <= _boundsMaxX; x++)
// 				for (var y = _boundsMinY; y <= _boundsMaxY; y++)
// 					if (this[x, y].IsPrimary)
// 						for (int dirIdx = 0; dirIdx < 4; dirIdx++) {
// 							bool hasJumpPointAtThisAxis = false;
// 							bool hit = SendFromThisPoint(x, y, dirIdx, ref hasJumpPointAtThisAxis);
// 							if (hasJumpPointAtThisAxis && !hit) {
// 								this[x, y].Send[dirIdx] = true;
// 							}
// 						}
// 		}

// 		private bool SendFromThisPoint(int x, int y, int dirIdx, ref bool hasJumpPointAtThisAxis) {
// 			var offset = JPSUtils.DirToVec[dirIdx];
// 			var nx = x + offset.x;
// 			var ny = y + offset.y;
// 			// 遇到障碍物终止发散
// 			if (!_N(nx, ny)) return true;
// 			// 反转方向并修改Send
// 			var oppDirIdx = JPSUtils.OppositeDirIdx[dirIdx];
// 			var cell = this[nx, ny];
// 			cell.Send[oppDirIdx] = true;
// 			cell.IsStraight = true;
// 			if (cell.IsPrimary)
// 				hasJumpPointAtThisAxis = true;
// 			// 递归了
// 			SendFromThisPoint(nx, ny, dirIdx, ref hasJumpPointAtThisAxis);
// 			return false;
// 		}

// 		private void CalcPrimaryJP() {
// 			for (var x = _boundsMinX; x <= _boundsMaxX; x++)
// 				for (var y = _boundsMinY; y <= _boundsMaxY; y++) {
// 					if (!_N(x, y)) continue;
// 					var g = this[x, y];
// 					bool n = _N(x, y + 1),
// 						 s = _N(x, y - 1),
// 						 e = _N(x + 1, y),
// 						 w = _N(x - 1, y),
// 						 ne = !_N(x + 1, y + 1),
// 						 nw = !_N(x - 1, y + 1),
// 						 se = !_N(x + 1, y - 1),
// 						 sw = !_N(x - 1, y - 1);
// 					if (n && e && ne) {
// 						g.Recv[(int)JPSDir.N] = true;
// 						g.Recv[(int)JPSDir.E] = true;
// 						g.IsPrimary = true;
// 					}
// 					if (n && w && nw) {
// 						g.Recv[(int)JPSDir.N] = true;
// 						g.Recv[(int)JPSDir.W] = true;
// 						g.IsPrimary = true;
// 					}
// 					if (s && w && sw) {
// 						g.Recv[(int)JPSDir.S] = true;
// 						g.Recv[(int)JPSDir.W] = true;
// 						g.IsPrimary = true;
// 					}
// 					if (s && e && se) {
// 						g.Recv[(int)JPSDir.S] = true;
// 						g.Recv[(int)JPSDir.E] = true;
// 						g.IsPrimary = true;
// 					}
// 				}

// 		}

// 		internal void Clear() {
// 			if (_grid != null)
// 				foreach (var g in _grid)
// 					g.Revert();
// 		}

// 		internal bool _N(int x, int y) {
// 			return InBounds(x, y) && _navigable[x, y];
// 		}

// 		internal bool InBounds(int x, int y) {
// 			return x >= _boundsMinX && x <= _boundsMaxX &&
// 				   y >= _boundsMinY && y <= _boundsMaxY;
// 		}
// 	}

// 	internal class JPSPlusPath : PathFinder {
// 		private readonly JPSPlusGrid _grid;
// 		private Vector2Int _start = JPSUtils.NullVec, _goal = JPSUtils.NullVec;
// 		private readonly FastPriorityQueue<JPSPlusNode> _open;

// 		public JPSPlusPath(JPSPlusGrid grid, int cap = 256) {
// 			_grid = grid;
// 			_open = new FastPriorityQueue<JPSPlusNode>(cap);
// 		}

// 		public override List<Vector2Int> FindPath(Vector2Int start, Vector2Int goal) {
// 			if (!_grid._N(start.x, start.y) || !_grid._N(goal.x, goal.y))
// 				return null;
// 			_grid.Clear();
// 			_start = start;
// 			_goal = goal;
// 			_open.Clear();
// 			var startNode = _grid[start];
// 			_open.Enqueue(startNode, startNode.GivenCost);
// 			while (_open.Count != 0) {
// 				JPSPlusNode current = _open.Dequeue();
// 				current.ListState = 2;
// 				if (current.Location == goal)
// 					return Trace(current);
// 				IdentitySuccessors(current);
// 			}
// 			return null;
// 		}

// 		private void IdentitySuccessors(JPSPlusNode current) {
// 			foreach (var direction in GetValidDir(current)) {
// 				if (useBB && !BB.IsCellInBoundingBox(current.Location, direction, _goal))
// 					continue;
// 				JPSPlusNode newSuccessor = null;
// 				float givenCost = 0;
// 				// 水平方向，立刻到达
// 				if (IsCardinal(direction) &&
// 					IsGoalInThisDirExactly(_goal, current.Location, direction) &&
// 					DiffNode(_goal, current.Location) <= Mathf.Abs(current.Dist[(int)direction])
// 					) {
// 					newSuccessor = _grid[_goal];
// 					givenCost = current.GivenCost + DiffNode(_goal, current.Location);
// 				} else
// 				// 对角线上优先对齐到水平方向
// 				if (IsDiagonal(direction) &&
// 					IsGoalInThisDirGenerally(_goal, current.Location, direction) &&
// 					(DiffNode_x(_goal, current.Location) <= Mathf.Abs(current.Dist[(int)direction]) ||
// 					DiffNode_y(_goal, current.Location) <= Mathf.Abs(current.Dist[(int)direction]))) {
// 					int min_diff = Mathf.Min(Mathf.Abs(_goal.x - current.Location.x),
// 											 Mathf.Abs(_goal.y - current.Location.y));
// 					newSuccessor = _grid[current.Location + JPSUtils.DirToVec[(int)direction] * min_diff];
// 				} else
// 				// 能走就走
// 				if (current.Dist[(int)direction] > 0) {
// 					newSuccessor = _grid[current.Location + JPSUtils.DirToVec[(int)direction] * current.Dist[(int)direction]];
// 					givenCost = DiffNode(newSuccessor.Location, current.Location);
// 					if (IsDiagonal(direction)) {
// 						givenCost = givenCost * JPSUtils.SQRT2;
// 					}
// 					givenCost += current.GivenCost;
// 				}
// 				// 传统A*
// 				if (newSuccessor != null) {
// 					// 如果既不在open也不在closed
// 					if (newSuccessor.ListState == 0) {
// 						newSuccessor.Parent = current;
// 						newSuccessor.GivenCost = givenCost;
// 						newSuccessor.dirFromParent = direction;
// 						newSuccessor.FinalCost = givenCost + Heuristic(newSuccessor.Location, _goal);
// 						newSuccessor.ListState = 1;
// 						_open.Enqueue(newSuccessor, newSuccessor.FinalCost);
// 					} else if (givenCost < newSuccessor.GivenCost) {
// 						newSuccessor.Parent = current;
// 						newSuccessor.GivenCost = givenCost;
// 						newSuccessor.dirFromParent = direction;
// 						newSuccessor.FinalCost = givenCost + Heuristic(newSuccessor.Location, _goal);
// 						if (newSuccessor.ListState == 1)
// 							_open.UpdatePriority(newSuccessor, newSuccessor.FinalCost);
// 					}
// 				}
// 			}
// 		}

// 		/// 估价函数
// 		private float Heuristic(Vector2Int current, Vector2Int _goal) {
// 			var diff = _goal - current;
// 			diff.x = Mathf.Abs(diff.x);
// 			diff.y = Mathf.Abs(diff.y);
// 			return (Mathf.Max(diff.x, diff.y) + (JPSUtils.SQRT2 - 1) * Mathf.Min(diff.x, diff.y));
// 		}

// 		// 判断方向的类型
// 		private bool IsCardinal(JPSDir dir) {
// 			return dir <= JPSDir.W;
// 		}
// 		private bool IsDiagonal(JPSDir dir) {
// 			return dir >= JPSDir.NE;
// 		}

// 		/// 目标是否大致在这个方向
// 		private bool IsGoalInThisDirGenerally(Vector2Int goal, Vector2Int current, JPSDir dir) {
// 			Vector2Int delta = goal - current;
// 			switch (dir) {
// 				case JPSDir.E:
// 					return delta.x > 0 && delta.y == 0;
// 				case JPSDir.N:
// 					return delta.y > 0 && delta.x == 0;
// 				case JPSDir.NE:
// 					return delta.x > 0 && delta.y > 0;
// 				case JPSDir.W:
// 					return delta.x < 0 && delta.y == 0;
// 				case JPSDir.NW:
// 					return delta.x < 0 && delta.y > 0;
// 				case JPSDir.S:
// 					return delta.y < 0 && delta.x == 0;
// 				case JPSDir.SE:
// 					return delta.y < 0 && delta.x > 0;
// 				case JPSDir.SW:
// 					return delta.y < 0 && delta.x < 0;
// 			}
// 			return false;
// 		}
// 		/// 目标是否严格在这个方向上
// 		private bool IsGoalInThisDirExactly(Vector2Int goal, Vector2Int current, JPSDir dir) {
// 			Vector2Int delta = goal - current;
// 			switch (dir) {
// 				case JPSDir.E:
// 					return delta.x > 0 && delta.y == 0;
// 				case JPSDir.N:
// 					return delta.y > 0 && delta.x == 0;
// 				case JPSDir.NE:
// 					return delta.x > 0 && delta.y > 0 && Mathf.Abs(delta.x) == Mathf.Abs(delta.y);
// 				case JPSDir.W:
// 					return delta.x < 0 && delta.y == 0;
// 				case JPSDir.NW:
// 					return delta.x < 0 && delta.y > 0 && Mathf.Abs(delta.x) == Mathf.Abs(delta.y);
// 				case JPSDir.S:
// 					return delta.y < 0 && delta.x == 0;
// 				case JPSDir.SE:
// 					return delta.y < 0 && delta.x > 0 && Mathf.Abs(delta.x) == Mathf.Abs(delta.y);
// 				case JPSDir.SW:
// 					return delta.y < 0 && delta.x < 0 && Mathf.Abs(delta.x) == Mathf.Abs(delta.y);
// 			}
// 			return false;
// 		}

// 		/// 计算差值
// 		private int DiffNode(Vector2Int x, Vector2Int y) {
// 			var diff = x - y;
// 			return Mathf.Max(Mathf.Abs(diff.x), Mathf.Abs(diff.y));
// 		}
// 		private int DiffNode_x(Vector2Int x, Vector2Int y) {
// 			var diff = x - y;
// 			return Mathf.Abs(diff.x);
// 		}
// 		private int DiffNode_y(Vector2Int x, Vector2Int y) {
// 			var diff = x - y;
// 			return Mathf.Abs(diff.y);
// 		}

// 		private JPSDir[] GetValidDir(JPSPlusNode current) {
// 			return current.Parent == null ? JPSUtils.allDirections : JPSUtils.ValidDirLookUpTable[current.dirFromParent];
// 		}

// 		private List<Vector2Int> Trace(JPSPlusNode node) {
// 			var path = new List<Vector2Int> { node.Location };
// 			while (node.Parent != null) {
// 				node = node.Parent;
// 				path.Add(node.Location);
// 			}
// 			path.Reverse();
// 			return path;
// 		}
// 	}
// }